class Solution {
    public:
    int splitArray(vector<int>& nums, int k) {
            int n = nums.size();
            int lhs = *max_element(nums.begin(),nums.end());
            int rhs = 1e9;
    
            auto check = [&](int mid){
                int sum = 0,tmp = 1;
                for(int i : nums){
                    sum += i;
                    if(sum > mid){
                        sum = i,tmp++;
                    }
                    if(tmp > k)
                        return false;
                }    
                return true;
            };
    
            while(lhs <= rhs){
                // cout << left <<' ' <<right << endl;
                int mid = (lhs + rhs) >> 1;
                if(check(mid)){
                    rhs = mid - 1;
                }else{
                    lhs = mid + 1;
                }
            }
            return lhs;
    }
};


    class Solution {
        public:
            int minimizedMaximum(int n, vector<int>& quantities) {
                int left = 1,
                    right = *max_element(quantities.begin(), quantities.end());
                auto check = [&](int mid) {
                    if(mid == 0){
                        return true;
                    }
                    int tmp = 0;
                    for (int i : quantities) {
                        tmp += i / mid + (i % mid != 0);
                        if (tmp > n)
                            return false;
                    }
                    return true;
                };
        
                while (left <= right) {
                    int mid = (left + right) >> 1;
                    if (check(mid)) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                return left;
            }
        };
        class Solution {
            public:
                int minimumSize(vector<int>& nums, int maxOperations) {
                    int left = 1,right = *max_element(nums.begin(),nums.end());
                    auto check = [&](int mid){
                        int tmp = 0;
                        for(int i : nums){
                            tmp += (i-1) / mid;
                            if(tmp > maxOperations){
                                return false;
                            }
                        }
                        return true;
                    };
            
            
            
                    while(left <= right){
                        int mid = (left + right) >> 1;
                        if(check(mid)){
                            right = mid - 1;
                        }else{
                            left = mid + 1;
                        }
                    }
                    return left;
                }
            };
            class Solution {
                public:
                    int minimumEffortPath(vector<vector<int>>& heights) {
                        int n = heights.size(), m = heights[0].size();
                        if(n == 1 && m == 1)
                            return 0;
                        int num[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                        auto dfs = [&](int mid) {
                            queue<pair<int, int>> q;
                            vector<vector<bool>> rember(n, vector<bool>(m, false));
                            q.push({0, 0});
                            int x, y, px, py;
                            while (q.size()) {
                                auto [px, py] = q.front();
                                q.pop();
                                for (int i = 0; i < 4; i++) {
                                    x = px + num[i][0], y = py + num[i][1];
                                    if (x < 0 || y < 0 || x >= n || y >= m || rember[x][y])
                                        continue;
                                    if (abs(heights[x][y] - heights[px][py]) > mid)
                                        continue;
                                    if (x == n - 1 && y == m - 1)
                                        return true;
                                    q.push({x, y});
                                    rember[x][y] = true;
                                }
                            }
                            return false;
                        };
                        int left = 0, right = 999999;
                        while (left <= right) {
                            int mid = (left + right) >> 1;
                            if (dfs(mid)) {
                                right = mid - 1;
                            } else {
                                left = mid + 1;
                            }
                        }
                        return left;
                    }
                };

                class Solution {
                    public:
                        int minimizeArrayValue(vector<int>& nums) {
                            int n = nums.size();
                            auto check = [&](int mid){
                                long long old = 0;
                                for(int i : nums){
                                    old += (mid - i);
                                    if(old < 0){
                                        return false;
                                    }
                                }
                                return true;
                            };
                    
                    
                            int left = 0,right = *max_element(nums.begin(),nums.end());
                            while(left <= right){
                                int mid = (left + right) >> 1;
                                if(check(mid)){
                                    right = mid - 1;
                                }else{
                                    left = mid + 1;
                                }
                            }
                            return left;
                        }
                    };

            
    class Solution {
        public:
            int minCapability(vector<int>& nums, int k) {
                int left = 0, right = *max_element(nums.begin(), nums.end()),
                    n = nums.size();
                auto check = [&](int mid) {
                    int tmp = 0;
                    for (int i = 0; i < n; i++) {
                        if (nums[i] <= mid) {
                            i++;
                            tmp++;
                            if (tmp >= k) {
                                return true;
                            }
                        }
                    }
                    cout << tmp << endl;
        
                    return false;
                };
                while (left <= right) {
                    // cout << left << ' ' << right << endl;
                    int mid = (left + right) >> 1;
                    if (check(mid)) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                return left;
            }
        };
        class Solution {
            public:
                int m[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                int swimInWater(vector<vector<int>>& grid) {
                    int n = grid.size();
                    if(n == 1){
                        return grid[0][0];
                    }
                    int left = grid[0][0], right = 2500;
                    auto bfs = [&](int mid) {
                        queue<pair<int, int>> q;
                        vector t(n, vector<bool>(n, false));
                        q.push({0, 0});
                        int qx, qy, x, y;
                        while (q.size()) {
                            auto [qx, qy] = q.front();
                            q.pop();
                            for (int i = 0; i < 4; i++) {
                                x = qx + m[i][0], y = qy + m[i][1];
                                if (x < 0 || x >= n || y < 0 || y >= n || t[x][y])
                                    continue;
                                if (grid[x][y] > mid)
                                    continue;
                                if (x == n - 1 && y == n - 1)
                                    return true;
                                t[x][y] = true;
                                q.push({x, y});
                            }
                        }
                        return false;
                    };
                    while (left <= right) {
                        int mid = (left + right) >> 1;
                        if (bfs(mid)) {
                            right = mid - 1;
                        } else {
                            left = mid + 1;
                        }
                    }
                    return left;
                }
            };

            class Solution {
                public:
                    int minimizeMax(vector<int>& nums, int p) {
                        if(p == 0) return 0;
                        ranges::sort(nums);
                        int n = nums.size();
                        vector<int> tmp(n - 1);
                        for(int i = 1;i <n;i++){
                            tmp[i - 1] = nums[i] - nums[i - 1];
                        }
                        n--;
                        int left = 0,right = *max_element(nums.begin(),nums.end());
                        auto check = [&](int mid){
                            int a = 0;
                            for(int i = 0;i < n;i++){
                                if(tmp[i] <= mid){
                                    i++;
                                    a++;
                                    if(a >= p){
                                        return true;
                                    }
                                }
                            }
                            return false;
                        };
                        while(left <= right){
                            int mid = (left + right) >> 1;
                            if(check(mid)){
                                right = mid - 1;
                            }else{
                                left = mid + 1;
                            }
                        }
                        return left;
                    }
                };

                class Solution {
                    public:
                        int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
                                    if (edges.size() < n - 1) {
                                return -1;
                            }
                            int m = edges.size();
                            int left = 0, right = 1000000;
                            int move = 0;
                            auto check = [&](int mid) {
                                vector<bool> t(n,false);         // 可否到达0点
                                // vector<int> out(n,0);        // 出度数
                                vector<vector<int>> vv(n); // 图
                                for (auto& v : edges) {
                                    if (v[2] > mid)
                                        continue;
                                    vv[v[1]].push_back(v[0]);
                                    // if (++out[v[0]] > threshold) {
                                    //     // 出度数超了,mid需要变小
                                    //     move = 1;
                                    //     return false;
                                    // }
                                }
                                auto fun = [&](this auto&& fun, int i) {
                                    if (t[i] == true)
                                        return;
                                    t[i] = true;
                                    for (int ii : vv[i]) {
                                        fun(ii);
                                    }
                                };
                                fun(0);
                                for (bool a : t) {
                                    if (a == false) {
                                        // 有一个地方走不到,mid需要变大
                                        return false;
                                    }
                                }
                                // mid需要变小
                                return true;
                            };
                            while (left <= right) {
                                int mid = (left + right) >> 1;
                                if (check(mid)) {
                                    right = mid - 1;
                                } else {
                                    left = mid + 1;
                                }
                            }
                            if (check(left) == false)
                                return -1;
                            else
                                return left;
                        }
                    };
                    using ll =long long;
                    class Solution {
                    public:
                    int gcd(int a, int b) {
                        while (b != 0) {
                            int temp = b;
                            b = a % b;
                            a = temp;
                        }
                        return a;
                    }
                        ll fun(ll a,ll b){
                            // 最小公倍数
                            return a /gcd(a,b) * b;
                        }
                        int minimizeSet(int d1, int d2, int u1, int u2) {
                            ll tmp = fun(d1,d2);
                            auto check = [&](int mid){
                                ll a = mid / d1, b = mid / d2, c = mid / tmp;
                                mid -= c, a -= c, b -= c;
                                if (mid - a < u1) return false;
                                if (mid - b < u2) return false;
                                if (u1 + u2 > mid) return false;
                                return true;
                            };
                            int left = 0,right = INT_MAX;
                            // int left = 0,right = 100;
                            while(left < right){
                                // cout << left << ' '<< right << endl;
                                int mid = left + ((right - left)>>1);
                                // int mid = (left + right) >> 1;
                                if(check(mid)){
                                    right = mid;
                                }else{
                                    left = mid + 1;
                                }
                            }
                            return left;
                        }
};
class Solution {
    public:
        int minLength(string s, int numOps) {
            int n = s.size();
            auto check = [&](int m) {
                int cnt = 1, a = 0;
                if (m == 1) {
                    for (int i = 0; i < n; i++) {
                        a += ((s[i] - '0')^i)&1;
                    }
                    return min(a,n - a) <= numOps;
    
                } else {
                    for (int i = 1; i <= n; i++) {
                        if (s[i] == s[i - 1] && i < n) {
                            cnt++;
                        } else {
                            a += cnt / (m + 1);
                            if (a > numOps) {
                                return false;
                            }
                            cnt = 1;
                        }
                    }
                    return true;
                }
            };
    
            int left = 1, right = n;
            while (left <= right) {
                int mid = (left + right) >> 1;
                if (check(mid)) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        }
    };
    class Solution {
        public:
            int minTime(vector<int>& time, int m) {
                int n = time.size();
                auto check = [&](int mid){
                    int t = m,pos = 0;
                    while(t--){
                        int cnt = 0,tmp = 0;
                        while(pos < n){
                            tmp = max(tmp,time[pos]);
                            if(cnt + time[pos] - tmp > mid){
                                // pos++;
                                break;
                            }else{
                                cnt += time[pos++];
                            }
                        }
                    }
                    return pos == n;
                };
                int left = 0,right = INT_MAX/2;
                while(left <= right){
                    int mid = (left + right)>>1;
                    if(check(mid)){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
                return left;
            }
        };